/*
 * @lc app=leetcode.cn id=707 lang=java
 *
 * [707] 设计链表
 */

// @lc code=start

class ListNode {
  int val;
  ListNode next;
  ListNode prev;

  ListNode(int x) {
    val = x;
  }
}

class MyLinkedList {
  private ListNode head;
  private ListNode tail;
  int size;

  /** Initialize your data structure here. */
  public MyLinkedList() {
    head = new ListNode(0);
    tail = new ListNode(0);
    size = 0;
    head.next = tail;
    tail.prev = head;
  }

  /**
   * Get the value of the index-th node in the linked list. If the index is
   * invalid, return -1.
   */
  public int get(int index) {
    if (index < 0 || index >= size) {
      return -1;
    }
    ListNode ans;
    if (index + 1 < size - index) {
      ans = head;
      for (int i = 0; i < index+1; i++) {
        ans = ans.next;
      }
    } else {
      ans = tail;
      for (int i = 0; i < size - index; i++) {
        ans = ans.prev;
      }
    }
    return ans.val;
  }

  /**
   * Add a node of value val before the first element of the linked list. After
   * the insertion, the new node will be the first node of the linked list.
   */
  public void addAtHead(int val) {
      ListNode p = head;
      ListNode ans = new ListNode(val);
      ans.prev = p;
      ans.next = p.next;
      p.next.prev = ans;
      p.next = ans;
      size++;
  }

  /** Append a node of value val to the last element of the linked list. */
  public void addAtTail(int val) {
      ListNode p = tail;
      ListNode ans = new ListNode(val);
      ans.next = p;
      ans.prev = p.prev;
      p.prev.next = ans;
      p.prev = ans;
      size++;

  }

  /**
   * Add a node of value val before the index-th node in the linked list. If index
   * equals to the length of linked list, the node will be appended to the end of
   * linked list. If index is greater than the length, the node will not be
   * inserted.
   */
  public void addAtIndex(int index, int val) {
      if(index > size){
        return;
      }
      if(index < 0){
        index = 0;
      }
      ListNode pre, succ;
      if (index < size / 2) {
        pre = head;
        for (int i = 0; i < index; i++) {
          pre = pre.next;
        }
        succ = pre.next;
      } else {
        succ = tail;
        for (int i = 0; i < size - index; i++) {
          succ = succ.prev;
        }
        pre = succ.prev;
      }
      
      ListNode ans = new ListNode(val);
      ans.next = succ;
      ans.prev = pre;
      pre.next = ans;
      succ.prev = ans;
      size++;
  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  public void deleteAtIndex(int index) {
    if(index >= size || index < 0){
      return;
    }
    ListNode pre, succ;
    if (index < size / 2) {
      pre = head;
      for (int i = 0; i < index; i++) {
        pre = pre.next;
      }
      succ = pre.next.next;
    } else {
      succ = tail;
      for (int i = 0; i < size - index-1; i++) {
        succ = succ.prev;
      }
      pre = succ.prev.prev;
    }
    
    pre.next = succ;
    succ.prev = pre;
    size--;
  }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList(); int param_1 = obj.get(index);
 * obj.addAtHead(val); obj.addAtTail(val); obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
// @lc code=end
